package Year22_Month03.day29;

import java.util.Scanner;

public class Main3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            String s  = sc.nextLine();
            String[] arr = s.split("<br/>");
            StringBuilder mystring = new StringBuilder();
            for (int i = 0; i < arr.length; i++) {
                if(i < arr.length - 1){
                    mystring.append(fib(Integer.valueOf(arr[i])) + "<br/>");
                    continue;
                }
                mystring.append(fib(Integer.valueOf(arr[i])));
            }
            System.out.println(mystring.toString());
        }
    }

    public static String fib(int a){
        if(a == 1){
            return "1";
        }
        if(a == 2){
            return "2";
        }
        int left = 1;
        int right = 2;
        int tmp = 0;
        for (int i = 3; i <= a; i++) {
            tmp = left + right;
            left = right;
            right = tmp;
        }
        String s = String.valueOf(tmp);
        if(s.length() <= 6)
        {
            return s;
        }
        int sss  = tmp % 1000000;
        return String.valueOf(sss);
    }
}
